// This sudoku implementation uses a lot of bitwise calculation.
// This file extends the build-in Number type to support additional bitwise functions. 

// The following function gets the rightmost bit that is set. (Unused, presented as example)
/*
function RightmostBit(value)
{
	return value & ~(value - 1);
}
*/

// Use anonymous function closure to hide some variables. 
(function ()
{
	var BcCache = [];

	for (var i = 0; i < 512; i++)
	{
		var count = 0, value = i;
		while (value)
		{
			value &= value - 1; // clear the least significant bit set
			count++;
		}
		BcCache[i] = count;
	}

	// Quickly determine if a number is a power of two.
	// In terms of bitwise representation, it means the bitvalue has only one bit set.
	// Note that having valueOf() is faster
	Number.prototype.isPowerOfTwo = function ()
	{
		var value = this.valueOf();
		if (value < 512) return BcCache[value] == 1;
		return ((value - 1) & value) === 0;
	}

	// Count the number of bits set to 1 in a bit value.
	Number.prototype.bitCount = function ()
	{
		var value = this.valueOf();

		if (value < 512) return BcCache[value];

		var count = 0;
		while (value) 
		{
			value &= value - 1; // clear the least significant bit set
			count++;
		}
		return count;
	}
})();

// split a bitvalue into each individual bits.
Number.prototype.splitBinary = function ()
{
	var value = this.valueOf();
	var bits = [];
	while (value)
	{
		bits.push(value & ~(value - 1));
		value &= value - 1;
	}
	return bits;
}

// ==================================================
// The following are not natural bitwise calculations
// They are specific functions designed for this implementation

// Convert a digit to bitmask
// Note that having valueOf() is faster
Number.prototype.digitToBitmask = function  ()
{
	return this.valueOf() ? (1 << (this.valueOf() - 1)) : 0;
}

// Convert a bitmask to digit
// switch is faster than shift loop
Number.prototype.bitmaskToDigit = function ()
{
/*
	var i = 1;
	while (digit >>>= 1) i++;
	return i;
*/
	switch(this.valueOf())
	{
		case 1: return 1;
		case 2: return 2;
		case 4: return 3;
		case 8: return 4;
		case 16: return 5;
		case 32: return 6;
		case 64: return 7;
		case 128: return 8;
		case 256: return 9;
		default: return 0;
	}
}

// Returns a string with all candidates. Compare to an array, string is easier to search.
// If pad parameter is used, it would fill the spot of unset digit.
Number.prototype.bitmaskToString = function (pad)
{
	var value = this.valueOf();
	var s = '';
	if (arguments.length === 0)
	{
		for (var i = 1; i < 10; i++)
		{
			if (value & 1) s += i;
			value >>>= 1; // shift bits right
		}
	}
	else
	{
		for (var i = 1; i < 10; i++)
		{
			if (value & 1) s += i;
			else s += pad;
			value >>>= 1; // shift bits right
		}
	}
	return s;
}
